Paavola kwam in totaal 23 keer uit voor de nationale ploeg van Finland in de periode 1986-1994. Hij maakte zijn debuut onder leiding van bondscoach Martti Kuusela op 9 september1986 in de vriendschappelijke thuiswedstrijd tegen Oost-Duitsland (1-0) in Lappeenranta, net als Miika Juntunen (Örgryte IS) en Mika-Matti Paatelainen (Valkeakosken Haka). Hoewel Oost-Duitsland aantrad met de olympische selectie geldt de wedstrijd als een officiële A-interland voor Finland. Paavola trad in dat duel na 68 minuten aan als vervanger van aanvoerder Jari Niinimäki (AIK Solna).
HJK Helsinki